package madixin.t538;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class Solution {
    //方法1:
    //1.中序遍历,生成有序数组
    //2.累加综合
    //3.循环数组，修改
    public TreeNode convertBST2(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        midOrder(root, list);
        int sum = 0;
        for (TreeNode node : list) {
            sum += node.val;
        }

        for (int i = 0; i < list.size() - 1; i++) {
            TreeNode node = list.get(i);
            int old = node.val;
            node.val = sum;
            sum -= old;
        }

        return root;
    }

    private void midOrder(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        midOrder(root.left, list);
        list.add(root);
        midOrder(root.right, list);
    }

    //方法2：先遍历右子树
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        travel(root);

        return root;
    }

    private void travel(TreeNode root) {
        if (root == null) {
            return;
        }
        travel(root.right);
        sum += root.val;
        root.val = sum;
        travel(root.left);
    }


}